

		TORT
               ------

(Mihai Stroe)

	Gigel a primit de ziua lui un tort dreptunghiular pe care mama
lui a desenat un caroiaj. In mijlocul anumitor patratele sunt asezate
bezele, una intr-un patratel. Gigel ar vrea sa manance cat mai multe
bzele, dar tatal lui a inventat o smecherie prin care spera sa reduca
pofta de bezele a lui Gigel. Gigel a primit si o multime de bucati de
ciocolata. Tatal lui ii cere sa inlocuiasca bezelele pe care vrea sa
le manance cu bucati de ciocolata, formate din 2 patratele. Gigel tre-
buie sa inlocuiasca intotdeauna cate 2 bezele (vecine pe orizontala sau
verticala), fara a suprapune bucatile de ciocolata.

Cerinta

	Stiind ca exista suficiente bucati de cioclata, ajutati-l pe
Gigel sa inlocuiasca cat mai multe bezele, respectand regulile impuse
de tatal lui.

Date de intrare:

Fisier de intrare: TORT.IN

Linia 1: M N
- 2 numere naturale nenule, separate printr-un spatiu, reprezentand di-
  mensiunile caroiajului de pe tort

Liniile 2..M+1:
  t11 t12 .. t1N
  ..............
  tM1 tM2 .. tMN

- codificarea caroiajului de pe tort, linie dupa linie: valoarea 1 repre-
  zinta o bezea, 0 inseamna ca in patratelul respectiv nu exista bezea;
  intre 2 valori numerice exista un singur spatiu

Date de iesire:

Fisier de iesire: TORT.OUT

Linia 1: K
- numar natural, reprezentand numarul bucatilor de ciocolata (o bucata
este formata din 2 patratele, deci va inlocui 2 bezele); acest numar
trebuie sa fie cel mai mare posibil, respectand cerintele problemei; o
bucata de ciocolata, formata din 2 patratele nu se poate rupe in doua

Liniile 2..K+1: Xi Yi Di
- urmatoarele K linii contin cate 2 numere naturale nenule si un carac-
ter, separate prin cate un spatiu, care descriu amplasarea unei bucati de
ciocolata; Xi si Yi sunt coordonatele patratelului stanga sus, iar Di
identifica pozitia celuilalt patratel al bucatii astfel: 'E' (Est) sau
'S' (Sud), dupa cum al doilea patratel se afla la dreapta primului sau
sub primul.

Restrictii:
- 1<M,N<=100
- o bucata de ciocolata trebuie sa inlocuiasca exact 2 bezele
- bucatile de ciocolata nu se pot suprapune
- ordinea in fisierul de iesire a descrierii bucatilor poate fi oarecare

Exemplu:
TORT.IN			TORT.OUT
4 3			3
1 0 1			2 2 S
0 1 0			3 1 S
1 1 0			4 2 E
1 1 1

Timp maxim de executie/test: 1 secunda